/*
题目链接：https://leetcode.cn/problems/number-of-digit-one/
题目标题：233.数字1的个数
提交时间：2024.10.14
*/


class Solution {
public:
    int countDigitOne(int n) {
        string s=to_string(n);   //为了便于计算，将n转换为字符串s
        vector<vector<int>>dp(s.size(),vector<int>(s.size(),-1));  //记录前m位中1的个数
        auto dfs=[&](auto&&dfs,int i,int c,bool islimit)->int{  //采用lambda表达式，时间复杂度会比单独定义在函数外要更小点
        if(i==s.size()) return c;   //完成所有的计算
        if(!islimit && dp[i][c]>=0){   //之前已经计算过
            return dp[i][c];
        }
        int res=0;  //记录当前1的个数
        int up=islimit?s[i]-'0':9;  //上界，当前位是否受到限制
        for(int d=0;d<=up;d++){
            if(d==1)   //填入1，此时c++
            res+=dfs(dfs,i+1,c+1,islimit&&d==up);
            else
            res+=dfs(dfs,i+1,c,islimit&&d==up);
        }
        if(!islimit) dp[i][c]=res;   //若没有限制，说明计算结果可记录
        return res;
    };
        return dfs(dfs,0,0,true);
    }
};
